/*
 *    MomentNodeType.java
 *    Copyright (C) 2011 University of Waikato, Hamilton, New Zealand
 *    @author Maciek Jarka (www.admire-project.eu)
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */
package moa.associations;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

import weka.associations.Item;

/** Node of Moment tree
 * Algorithm is based on two operations:
 *  - addition - when new transactions appears in time window
 *  - deletion - when the last transaction disappears from the time window
 * @author maciek
 *
 */
public class MomentNode {

    // Properties of the node
    int support;

    MomentNodeType type;

    List<Item> items;

    List<MomentNode> children;

    // sum of transaction ids
    int tid_sum;

    MomentNode parent;

    static double minSupport;

    // map of closed itemsets in the tree
    static HashMap<MomentHashKey, MomentNode> ciMap = new HashMap<MomentHashKey, MomentNode>();

    static List<FPNode> fpHeaders;

    public MomentNode(MomentNodeType type) {
        support = 0;
        tid_sum = 0;
        this.type = type;
        items = new ArrayList<Item>();
        children = new ArrayList<MomentNode>();
    }

    public MomentNode(MomentNodeType type, List<Item> items, MomentNode parent) {
        this(type);
        this.items = items;
        this.parent = parent;
        calculateSupport();
        this.tid_sum = FPNode.headers.calculateTidSum(items);
    }

    public MomentNode(MomentNodeType type, Item item, MomentNode parent) {
        this(type);
        this.items = new ArrayList<Item>();
        this.items.add(item);
        this.parent = parent;
    }

    public void calculateSupport() {
        this.support = FPNode.headers.calculateSupport(this.items);


    }

    /**
     *
     * @return true if there is closed itemset containing all of items from current node
     */
    private boolean leftcheck() {
        MomentNode n;
        n = ciMap.get(new MomentHashKey(this.support, this.tid_sum));
        if (n != null) {
            if (n.items.containsAll(this.items)) {
                return true;
            }
        }
        return false;
    }

    public String toString() {
        String str = "";
        for (Item i : items) {
            str += i.getAttribute().name() + " ";
        }
        return str;
    }

    /** Updates the tree with new transaction
     *
     * @param t
     */
    public void addition(Transaction t) {
        List<MomentNode> F = new ArrayList<MomentNode>();
        if (!t.items.containsAll(this.items)) {
            return;
        }
        for (MomentNode childNode : this.children) {
            if (t.items.containsAll(childNode.items)) {
                childNode.support++;
                childNode.tid_sum += t.id;
                if (childNode.support == minSupport) {
                    //childNode.type = MomentNodeType.UNPROMISING_GATEWAY;
                    F.add(childNode);
                }
            }
        }
        for (MomentNode childNode : this.children) {
            if (t.items.containsAll(childNode.items)) {
                if (childNode.type == MomentNodeType.INFREQUENT_GATEWAY); else if (childNode.leftcheck()) {
                    childNode.type = MomentNodeType.UNPROMISING_GATEWAY;
                } else if (F.contains(childNode)) {
                    explore(childNode);
                } else {
                    for (MomentNode nc : F) {
                        List<Item> items = new ArrayList<Item>();
                        items.addAll(childNode.items);
                        //items.add(nc.items.get(nc.items.size() - 1));
                        Item newItem = nc.items.get(nc.items.size() - 1);
                        if (!items.contains(newItem)) {
                            items.add(newItem);
                            if (t.items.containsAll(items)) {
                                MomentNode n = new MomentNode(MomentNodeType.INTERMEDIATE, items, childNode);
                                if (!childNode.children.contains(n)) {
                                    childNode.children.add(n);
                                }
                            }
                        }

                    }
                    childNode.addition(t);
                    if (childNode.type == MomentNodeType.CLOSED) {
                        ciMap.put(new MomentHashKey(childNode.support, childNode.tid_sum), childNode);
                    }
                    boolean found = false;
                    for (MomentNode nc : childNode.children) {
                        if (nc.support == childNode.support) {
                            found = true;
                            break;
                        }
                    }
                    if (!found) {
                        childNode.type = MomentNodeType.CLOSED;
                        ciMap.put(new MomentHashKey(childNode.support, childNode.tid_sum), childNode);
                    }
                }
            }
        }
    }

    /** Removes transaction from the tree
     *
     * @param t
     */
    public void deletion(Transaction t) {
        List<MomentNode> F = new ArrayList<MomentNode>();
        if (!t.items.containsAll(this.items)) {
            return;
        }
        for (MomentNode childNode : this.children) {
            if (t.items.containsAll(childNode.items)) {
                childNode.support--;
                childNode.tid_sum -= t.id;
                if (childNode.support == minSupport) {
                    F.add(childNode);
                }
            }
        }
        for (MomentNode childNode : this.children) {
            if (t.items.containsAll(childNode.items)) {
                if (childNode.type == MomentNodeType.INFREQUENT_GATEWAY || childNode.type == MomentNodeType.UNPROMISING_GATEWAY) {
                    continue;
                } else if (F.contains(childNode)) {
                    childNode.children.clear();
                    childNode.type = MomentNodeType.INFREQUENT_GATEWAY;
                } else if (childNode.leftcheck()) {
                    childNode.children.clear();
                    childNode.type = MomentNodeType.UNPROMISING_GATEWAY;
                } else {
                    for (MomentNode nc : F) {
                        List<Item> items = new ArrayList<Item>();
                        items.addAll(childNode.items);
                        items.add(nc.items.get(nc.items.size() - 1));
                        if (t.items.containsAll(items)) {
                            MomentNode n = new MomentNode(MomentNodeType.INTERMEDIATE, items, childNode);
                            if (!childNode.children.contains(n)) {
                                childNode.children.remove(n);
                            }
                        }
                        childNode.deletion(t);
                        if (childNode.type == MomentNodeType.CLOSED) {
                            boolean found = false;
                            for (MomentNode n : childNode.children) {
                                if (n.support == childNode.support) {
                                    found = true;
                                    break;
                                }
                            }
                            if (found) {
                                childNode.type = MomentNodeType.INFREQUENT_GATEWAY;
                                ciMap.remove(new MomentHashKey(childNode.support, childNode.tid_sum));
                            } else {
                                // Update entry in hash table?
                            }
                        }

                    }
                }
            }
        }
    }

    public static void explore(MomentNode node) {
        if (node.support < minSupport) {
            node.type = MomentNodeType.INFREQUENT_GATEWAY;
        } else if (node.leftcheck()) {
            node.type = MomentNodeType.UNPROMISING_GATEWAY;
        } else {
            for (MomentNode n : node.parent.children.subList(node.parent.children.indexOf(node) + 1, node.parent.children.size())) {
                if (n.support >= minSupport) {
                    List<Item> items = new ArrayList<Item>();
                    items.addAll(node.items);
                    items.add(n.items.get(n.items.size() - 1));
                    MomentNode newChld = new MomentNode(MomentNodeType.INTERMEDIATE, items, node);
                    node.children.add(newChld);
                }

            }
            for (MomentNode n : node.children) {
                explore(n);
            }
            boolean found = false;
            for (MomentNode chldNode : node.children) {
                if (chldNode.support == node.support) {
                    node.type = MomentNodeType.INTERMEDIATE;
                    found = true;
                }
            }
            if (!found) {
                node.type = MomentNodeType.CLOSED;
                ciMap.put(new MomentHashKey(node.support, node.tid_sum), node);
            }
        }
    }

    public static class NodeComparator implements Comparator<MomentNode> {

        @Override
        public int compare(MomentNode o1, MomentNode o2) {

            if (o1.items.size() == o2.items.size()) {
                for (int i = 0; i < o1.items.size(); i++) {
                    if (o1.items.get(i) != o2.items.get(i)) {
                        return o2.items.get(i).compareTo(o1.items.get(i));
                    }
                }
            } else if (o1.items.size() > o2.items.size()) {
                return 1;
            } else if (o1.items.size() < o2.items.size()) {
                return -1;
            }
            return 0;
        }
    }

    public List<MomentNode> getFrequentNodes() {
        List<MomentNode> itemsets = new ArrayList<MomentNode>();
        for (MomentNode n : this.children) {
            if (n.support > minSupport) {
                itemsets.add(n);
            }
            itemsets.addAll(n.getFrequentNodes());
        }
        return itemsets;


    }
}
